1167. Minimum Cost to Connect Sticks
Medium

You have some number of sticks with positive integer lengths. These lengths are given as an array sticks, where sticks[i] is the length of the ith stick.

You can connect any two sticks of lengths x and y into one stick by paying a cost of x + y. You must connect all the sticks until there is only one stick remaining.

Return the minimum cost of connecting all the given sticks into one stick in this way.

 

Example 1:

Input: sticks = [2,4,3]
Output: 14
Explanation: You start with sticks = [2,4,3].
1. Combine sticks 2 and 3 for a cost of 2 + 3 = 5. Now you have sticks = [5,4].
2. Combine sticks 5 and 4 for a cost of 5 + 4 = 9. Now you have sticks = [9].
There is only one stick left, so you are done. The total cost is 5 + 9 = 14.

Example 2:

Input: sticks = [1,8,3,5]
Output: 30
Explanation: You start with sticks = [1,8,3,5].
1. Combine sticks 1 and 3 for a cost of 1 + 3 = 4. Now you have sticks = [4,8,5].
2. Combine sticks 4 and 5 for a cost of 4 + 5 = 9. Now you have sticks = [9,8].
3. Combine sticks 9 and 8 for a cost of 9 + 8 = 17. Now you have sticks = [17].
There is only one stick left, so you are done. The total cost is 4 + 9 + 17 = 30.

Example 3:

Input: sticks = [5]
Output: 0
Explanation: There is only one stick, so you don't need to do anything. The total cost is 0.

 

Constraints:

  • 1 <= sticks.length <= 104
  • 1 <= sticks[i] <= 104
Accepted
51,978
Submissions
79,517
Seen this question in a real interview before?
Companies
Related Topics
Similar Questions
Show Hint 1
How many times does every stick contribute to the answer?
Show Hint 2
Some of the sticks will be used more than the others. Which sticks should be used the most/least?
Show Hint 3
The sticks with long lengths cost a lot so we should use these the least.
Show Hint 4
What if we keep merging the two shortest sticks?

Average Rating: 4.89 (35 votes)

Premium Video

Video Solution


 

Solution Article


Approach 1: Greedy

Intuition and Algorithm

Always pick two of the smallest sticks to connect and continue doing this until you get only one stick. Let's see why this works.

Consider 4 sticks of the following lengths:

sticks=[a1,a2,a3,a4]sticks = [a_1, a_2, a_3, a_4]

Let's try to connect them left to right.

After first merge, we will have:

sticks=[(a1+a2),a3,a4],cost=(a1+a2)sticks = [(a_1 + a_2), a_3, a_4], cost = (a_1 + a_2)

After second merge, we will have:

sticks=[(a1+a2+a3),a4],cost=(a1+a2)+(a1+a2+a3)sticks = [(a_1 + a_2 + a_3), a_4], cost = (a_1 + a_2) + (a_1 + a_2 + a_3)

And finally, last stick will look like:

sticks=[(a1+a2+a3+a4)],cost=(a1+a2)+(a1+a2+a3)+(a1+a2+a3+a4)sticks = [(a_1 + a_2 + a_3 + a_4)], cost = (a_1 + a_2) + (a_1 + a_2 + a_3) +(a_1 + a_2 + a_3 + a_4)

The final cost can be re-written as: cost=(3a1+3a2+2a3+a4)cost = (3a_1 + 3a_2 + 2a_3 + a_4)

As we can see, the sticks which are connected first are included in the final cost more than the ones that are picked later. Hence, it is optimal to pick smaller sticks first to get the smallest cost.

Let's try to figure out which data structure will be optimal to perform following tasks:

  • Get two of the smallest sticks (stick1 and stick2) from the array.
  • Add one stick (stick1 + stick2) back to the array.

We can use a min heap data structure (which is, generally, implemented as a PriorityQueue in most languages) which gives us O(logN)O(\log{N}) complexity for both the operations.

Complexity Analysis

  • Time complexity : O(NlogN)O(N\log{N}), where NN is the length of the input array. Let's break it down:

    • Step 1) Adding NN elements to the priority queue will be O(NlogN)O(N\log{N}).

    • Step 2) We remove two of the smallest elements and then add one element to the priority queue until we are left with one element. Since each such operation will reduce one element from the priority queue, we will perform N1N-1 such operations. Now, we know that both add and remove operations take O(logN)O(\log{N}) in priority queue, therefore, complexity of this step will be O(NlogN)O(N\log{N}).

  • Space complexity : O(N)O(N) since we will store NN elements in our priority queue.

Report Article Issue

Comments: 11
shukria's avatar
Read More

The quality of these articles are getting better and better. Very well written!

24
Reply
Share
Report
james_wo's avatar
Read More

this is basically the algo for building a huffman coding tree

18
Show 1 reply
Reply
Share
Report
ahmarajeel's avatar
Read More

Can someone explain to me why this won't work?

class Solution {
    public int connectSticks(int[] sticks) {
        // just sort the array
        Arrays.sort(sticks);
        
        // current value is current + previous
        for (int i = 1; i < sticks.length; i++) {
            sticks[i] = sticks[i] + sticks[i -1];
        }
        
        // get the sum of all but first index
        int cost = 0;
        for (int i = 1; i < sticks.length; i++) {
            cost += sticks[i]; 
        }
        return cost;
    }
}

3
Show 3 replies
Reply
Share
Report
user3600W's avatar
Read More

Understanding how heaps and priority queues work is so important!

1
Reply
Share
Report
florin5's avatar
Read More

Nit : The solution mentions 'Approach 1: Greedy' which might make one think there is another approach described. there not :-)

1
Reply
Share
Report
jeshojiu's avatar
Read More

well written compared to other solutions

1
Reply
Share
Report
vyshnavkr's avatar
Read More

I think the time complexity for constructing a PriorityQueue should be O(N), and inserting into PriorityQueue should be O(NlogN):
https://stackoverflow.com/a/34697891

1
Reply
Share
Report
b_clodius's avatar
Read More

I really struggled on this until I realized I can "re-use" sticks already formed. Kept thinking it needed to append to existing stick. Once I realized that it was heap time!

0
Reply
Share
Report
pkboolean's avatar
Read More

Damn. Sucks I didnt come up with this, seems pretty straightforward after seeing solution :(

0
Show 1 reply
Reply
Share
Report
user8134x's avatar
Read More

I tried solving it like the following but it doesn't work. I don't understand why?

  public int connectSticks(int[] sticks) {
    if(sticks == null || sticks.length == 0)
        return 0;
    
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    
    for(int stick : sticks) {
        minHeap.offer(stick);
    }
    
    int prevCost = 0;
    int currentCost = minHeap.poll();
    while(!minHeap.isEmpty()) {
        int stick = minHeap.poll();
        
        currentCost += stick;
        
        prevCost += currentCost;
    }
    
    return prevCost;
}

0
Show 1 reply
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
05/29/2021 19:00Accepted112 ms24.2 MBcpp
/23
Contribute
|||
Saved
Trie
This list is empty.